/**
 * 链表：单链表，双向链表,结尾的next指向null,最开始的头部指向null
 * 循环环链表时，其最后一个结点的指针指向表头结点
 * 公有方法：find,insert，del
 */

/**
 * 
 * 
 */
function nodeList() {
    this.value = ''
    this.next = ''
}

function List() {
    this.value = ''
    this.next = ''
    this.head = ''
}

function findNode(currentNode, value) {
    while (currentNode.value !== value) {
        currentNode = currentNode.next
    }
    return currentNode
}

function findPrevNode(currentNode, node) {
    while (currentNode.next !== node) {
        currentNode = currentNode.next
    }
    return currentNode
}

function insertNode(data, key) {
    const node = nodeList(data)
    const currentNode = findNode(key)
    node.next = currentNode.next
    currentNode.next = node
}

function delNode(key) {
    const currentNode = findNode(key)
    const prevNode = findPrevNode(currentNode)
    prevNode.next = currentNode.next
}


/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    const rest = new ListNode()
    let list1 = l1
    let list2 = l2
    let currentNode = rest
    while (list1 && list2) {
        if (list1.val < list2.val) {
            currentNode.next = list1
            list1 = list1.next
        } else {
            currentNode.next = list2
            list2 = list2.next
        }
        currentNode = currentNode.next
    }
    if (list1) {
        currentNode.next = list1
    }
    if (list2) {
        currentNode.next = list2
    }
    return rest.next || []
}

function ListNode(val) {
    this.val = val;
    this.next = null;
}